1. Field of the Invention
This invention relates generally to memory systems, and particularly to Multi Level Cell (MLC) NAND flash memory and other types of storage devices using the same.
2. Background
Flash memory is a block-based non-volatile memory with each block organized into and made of various pages. For all practical purpose flash memory require sequential programming of pages within a block. A NAND flash memory is an array of cells organized in rows and columns. A group of cell in a row of array form a page. A page is unit of programming. A Multi Level Cell NAND flash Memory can be programmed to more than two threshold levels and hence can store more than one information bit. For example a four level cell can store two bits per cell, a first bit and a second bit, and an eight level cell can store 3 bits of information. Without loss of generality we will use an MLC with four level that can store two information bits per cell in the discussion that follows. The information bits are stored by programming cell threshold levels that is the memory cell has a threshold voltage in any one of four threshold voltage distributions corresponding to one of four states indicating data “11”, data “10”, data “00”, and data “01”, respectively. The group of first bits of a page of MLC NAND flash are referred to as lower page and the group of second bits of a page are referred to as an upper page. (for 3 bit per cell MLC we have lower, middle and upper page, corresponding to first, second and third information bits). This is one conventional naming of pages that is adopted in this application, other naming of pages all fall within the scope and spirit of the invention. One basic programming scheme is multi-page programming scheme. In multi-page programming scheme only one page is programmed into a MLC cell during each programming operation. As mentioned before the pages are programmed sequentially, but the upper page and lower page of a page of cells are not generally sequential page addresses. The relation between the page address of a lower page and upper page is generally dependant on manufacturer and part number. Table 1 below shows an exemplary correspondence between page number and lower/upper page of a page of cells for a flash having blocks with 128 pages and 64 pages of cells. In table below “Lower Page k (Lk)” referrers to lower page of kth page of cells and similarly “Upper Page k U(k)” referrers to upper page of kth page of cells.
TABLE 1Page #Lower/Upper page #0Lower Page 0 (L0)1Lower Page 1 (L1)2Upper Page 0 (U0)3Lower Page 2 (L2)4Upper Page 1 (U1)5Lower Page 3 (L3)6Upper Page 2 (U2). . .. . .. . .. . .121Lower Page 61 (L61)122Upper Page 60 (U60)123Lower Page 62 (L62)124Upper Page 61 (U61)125Lower Page 63 (L63)126Upper Page 62 (U62)127Upper Page 63 (U63)
Table 2 below shows another exemplary correspondence between page number and lower/upper page of a page of cells for a flash having blocks with 128 pages and 64 pages of cells.
TABLE 2Page #Lower/Upper page #0Lower Page 0 (L0)1Lower Page 1 (L1)2Lower Page 2 (L2)3Lower Page 3 (L3)4Upper Page 0 (U0)5Upper Page 1 (U1)6Lower Page 4 (L4)7Lower Page 5 (L5)8Upper Page 2 (U2)9Upper Page 3 (U3). . .. . .. . .. . .118LowerPage 60 (L60)119Lower Page 61 (L61)120Upper Page 58 (U58)121Upper Page 59 (L59)122LowerPage 62 (L62)123Lower Page 63 (L63)124Upper Page 60 (U60)125UpperPage 61 (U61)126Upper Page 62 (U62)127Upper Page 63 (U63)
In MLC NAND flash, Gray mapping is widely employed, to map/bits to one of 2l levels in a cell, to reduce the overall bit error rate. In NAND Flash, dominant errors are mainly from misdetection of two adjacent levels, which results in just one bit error among 1 bits under Gray mapping.
FIG. 1 shows a prior art exemplary process of multi-page programming for 2 bits/cell NAND flash employing gray coding. In the first step, the cell is programmed according to the first bit to be stored. If the first bit is 1, the cell should not be programmed and will stay in erased state. Otherwise, it will be programmed to a temporary level which is an intermediate state to transit to levels with index 00 and 01. In the second step, when to program the second bit, the first bit stored in this cell is sensed first, and then programming operation will be executed to program this cell to a level which is determined with the sensed result and the second bit to be programmed.
NAND memories are not intrinsically error-free but rely on error correction coding (ECC) to correct raw bit errors. Generally the ECC circuit is not on the NAND and located in a Flash Controller. The ECC performs encoding and decoding of codewords. Generally the encoding is systematic that is the codeword consists of data and redundancy appended to data. The page data is split into one or more segments and the redundancy for each segment appended to the segment and all segments written to a page. Few examples a BCH code correcting 60 bits in a segment of 1032 bytes would require 105 parity bits for a code rate of 0.907, another BCH code correcting 120 bits in a segment of 2064 bytes would require 225 parity bits for a code rate of 0.901.
FIG. 2a shows a prior art exemplary page layout were page data is split into N segments and segment data and redundancy are written to a page (for page address i). In FIG. 2b the segments in the prior art page layout are shown further split to a first part and a second part which makes no difference at all to the prior art but would help in the description of one embodiment of the invention that will be discussed later.
However, bits stored in each MLC memory cell are subject to different bit error rates. We can see the second bit's (upper page) error rate is two times that of first bit (lower page) (see “Techniques for embracing intra-cell unbalanced bit error characteristics in MLC NAND flash memory” by G. Dong December 2010 IEEE). In current practice, bits stored in upper and lower pages are protected using the same ECC tuned for the worst-case upper page bit error rate scenario, which results in over-protection for lower pages and not effectively using the ECC power on the lower page.
What is needed is a storage system with increased reliability.